package com.zhugang.week04;

/**
 * @program algorithms
 * @description: climbStairs
 * @author: chanzhugang
 * @create: 2022/06/15 19:06
 */
public class ClimbStairs {

    /**
     * 70. 爬楼梯
     *
     * @param n
     * @return
     */
    // 备忘录
    private int[] mem;

    public int climbStairs(int n) {
        mem = new int[n + 1];
        return f(n);
    }

    private int f(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (mem[n] != 0) {
            return mem[n];
        }
        mem[n] = f(n - 1) + f(n - 2);
        return mem[n];
    }

}